package com.sun.javaalgorithm.day04;

import java.util.Arrays;

/**
 * @version 1.0
 * @Package: com.sun.javaalgorithm.day04
 * @ClassName: Recursion
 * @Author: sgq
 * @Date: 2024/4/13 14:33
 * @Description: 单路递归
 */
public class SingleRecursion {

    /**
     * 递归实现【n阶乘】
     *
     * @param n
     * @return
     */
    public static int factorial(int n) {
        if (n == 1) {
            return 1;
        }
        return n * factorial(n - 1);
    }

    /**
     * 递归实现【正反序列打印字符串】
     *
     * @param str
     * @return
     */
    public static void printStr(String str, int index) {
        if (index == str.length()) {
            return;
        }
        System.out.println("正序打印:" + str.charAt(index));
        printStr(str, index + 1);
        System.out.println("逆序打印:" + str.charAt(index));
    }

    /**
     * 递归实现【二分查找】
     *
     * @param arr
     * @param start
     * @param end
     */
    public static int binary(int[] arr, int start, int end, int target) {
        if (start > end) {
            return -1;
        }
        int mid = (start + end) >>> 1;
        if (arr[mid] > target) {
            return binary(arr, start, mid - 1, target);
        } else if (arr[mid] < target) {
            return binary(arr, mid + 1, end, target);
        } else {
            return mid;
        }
    }

    /**
     * 递归实现【冒泡排序】
     *
     * @param arr
     * @param tailIndex
     */
    public static void bubble(int[] arr, int tailIndex) {
        if (tailIndex == 0) {
            return;
        }
        for (int i = 0; i < tailIndex; i++) {
            if (arr[i] > arr[i + 1]) {
                int temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
            }
        }
        bubble(arr, tailIndex - 1);
    }

    /**
     * 递归实现【冒泡排序】
     *
     * @param arr
     * @param tailIndex
     */
    public static void bubble2(int[] arr, int tailIndex) {
        if (tailIndex == 0) {
            return;
        }
        int lastIndex = 0;
        for (int i = 0; i < tailIndex; i++) {
            if (arr[i] > arr[i + 1]) {
                int temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
                lastIndex = i;
            }
        }
        if (lastIndex == 0) {
            return;
        }
        bubble(arr, tailIndex - 1);
    }

    /**
     * 递归实现【冒泡排序】
     *
     * @param arr
     * @param tailIndex
     */
    public static void bubble3(int[] arr, int tailIndex) {
        if (tailIndex == 0) {
            return;
        }
        int lastIndex = 0;
        for (int i = 0; i < tailIndex; i++) {
            if (arr[i] > arr[i + 1]) {
                int temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
                lastIndex = i;
            }
        }
        bubble(arr, lastIndex);
    }

    /**
     * 递归实现【插入排序】
     *
     * @param arr
     * @param tailIndex {5,4,3,2,1}
     */
    public static void insertSort1(int[] arr, int tailIndex) {
        if (tailIndex == arr.length) {
            return;
        }
        int i = tailIndex - 1; // 已排序最后一位元素的索引
        int t = arr[tailIndex]; // 未排序的第一个元素索引
        while (i >= 0 && arr[i] > t) {
            arr[i + 1] = arr[i];
            i--;
        }
        arr[i + 1] = t;
        insertSort1(arr, tailIndex + 1);
    }

    /**
     * 递归实现【插入排序】 在索引范围内排序
     *
     * @param arr
     * @param tailIndex
     */
    public static void insertSort2(int[] arr, int tailIndex, int highIndex) {
        if (tailIndex == highIndex + 1) {
            return;
        }
        int i = tailIndex - 1; // 已排序最后一位元素的索引
        int t = arr[tailIndex]; // 未排序的第一个元素索引
        while (i >= 0 && arr[i] > t) {
            arr[i + 1] = arr[i];
            i--;
        }
        arr[i + 1] = t;
        insertSort2(arr, tailIndex + 1, highIndex);
    }

    public static void main(String[] args) {
        int[] brr1 = {5, 4, 3, 2, 1};
        insertSort1(brr1, 1);
        Arrays.stream(brr1).forEach(item -> {
            System.out.println(item);
        });

        System.out.println("--------------");

        int[] brr2 = {5, 4, 3, 2, 1};
        insertSort2(brr2, 1, 2);
        Arrays.stream(brr2).forEach(item -> {
            System.out.println(item);
        });

        System.out.println("--------------");

        int[] brr = {5, 4, 3, 2, 1};
        bubble2(brr, brr.length - 1);
        Arrays.stream(brr).forEach(item -> {
            System.out.println(item);
        });

        System.out.println(factorial(1));
        System.out.println(factorial(5));

        printStr("abcd", 0);

        int[] arr = {1, 3, 5, 7, 89};
        System.out.println(binary(arr, 0, arr.length - 1, 1));
        System.out.println(binary(arr, 0, arr.length - 1, 3));
        System.out.println(binary(arr, 0, arr.length - 1, 5));
        System.out.println(binary(arr, 0, arr.length - 1, 7));
        System.out.println(binary(arr, 0, arr.length - 1, 100));
    }

}
